1. Technical Field
The present invention relates generally to an improved data processing system and in particular to a method and apparatus for processing graphics data. Still more particularly, the present invention relates to a method and apparatus for back-face culling of data representing an object.
2. Description of Related Art
Data processing systems, such as personal computers and workstations, are commonly utilized to run computer-aided design (CAD) applications, computer-aided manufacturing (CAM) applications, and computer-aided software engineering (CASE) tools. Engineers, scientists, technicians, and others employ these applications daily. These applications involve complex calculations, such as finite element analysis, to model stress in structures. Other applications include chemical or molecular modeling applications. CAD/CAM/CASE applications are normally graphics intensive in terms of the information relayed to the user. Data processing system users may employ other graphics intensive applications, such as desktop publishing applications. Many of these applications may involve the display of three dimensional objects in which an object is rendered or drawn as it actually appears.
The visualization of surfaces is an important application of three-dimensional computer graphics. This technology offers accurate shaded images of surfaces along with the ability to quickly render new shaded images from any viewpoint.
Most three-dimensional computer graphics systems are optimized to render polygons, not surfaces. For this reason surfaces are usually approximated with polygons to enhance graphical performance. This creates a trade-off between the accuracy of a surface""s image and the time required to produce it. For instance, a sphere may be approximated with a cube, which consists of only six polygons. The graphical performance on most three-dimensional computer graphics systems will be good in this case, but the accuracy to a sphere will be poor. As the number of polygons used in the approximation is increased the graphical performance suffers.
In many situations, one or more surfaces are used to represent the boundary of a solid. These surfaces each have a direction associated with them which identify the inside versus the outside of the solid. By approximating each surface with a mesh of polygons, surface directions may be substituted with polygonal directions, or normal vectors.
Normal vectors can be exploited during the rendering process to enhance graphical performance. By identifying whether a given normal vector points towards or away from the viewpoint, the corresponding polygon can be interpreted as being front-facing (visible) or back-facing (not visible). A technique called xe2x80x9cback-face cullingxe2x80x9d allows improvements in graphical performance by identifying and rendering only those polygons that are front-facing.
Conventional back-face culling is typically performed using the vector dot product. Given two three-dimensional vectors: a polygon normal vector, N, and an xe2x80x9ceyexe2x80x9d vector, E, denoting the image plane normal vector pointing out of the screen, the dot product of these vectors determines the visibility of the polygon.
Let N and E be three-dimensional vectors (ni, nj, nk) and (ei, ej, ek), respectively. The vector dot product is defined as DOT(N, E)=ni*ei+nj*ej+nk*ek.
If the dot product is positive, then the polygon""s front side is facing the image planexe2x80x94the polygon is front-facing and should be rendered. If the dot product is negative, then the polygon""s back side is facing the image planexe2x80x94the polygon is back-facing and should not be rendered. If the dot product is zero, then the polygon is perpendicular to the image planexe2x80x94the polygon is neither front nor back-facing and may or may not be rendered.
Although conventional back-face culling is a useful technique for improving graphical performance, it still requires three multiplications and two additions to be performed for each polygon. Therefore, it would be advantageous to have an improved method and apparatus for performing back-face culling without requiring as many operations to be performed for each polygon.
The present invention provides a method and apparatus in a data processing system for generating a two dimensional display of a three dimensional object. Data is received representing the three dimensional object. Back-face culling is performed using a data structure, wherein the data structure includes a set of predetermined visibility data derived from the results of dot products of normal vectors with eye vectors. The two dimensional display of the three dimensional object is generated using results of the back-face culling.